package list;

import java.util.HashSet;

/**题目：判断一个链表是否有环
 * @Author Gavin
 * @date 2021.12.28 22:17
 */
public class list_4 {
    //第一种方法：借助一个hashset集合来存储元素，如果集合中已经存在了。说明就有环出现
    //Time:O(n) Space:O(n)
    public boolean solution_1(ListNode head){
        HashSet<ListNode> set=new HashSet<>();
        while (head!=null){
            if(set.contains(head))return true;
            set.add(head);
            head=head.next;
        }
        return false;
    }
    //第二种方法，借助两个快慢指针进行循环
    public boolean solution_2(ListNode head){
        ListNode fast=head,slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)return true;
        }
        return false;
    }
}
